package chapter24;

public class Chapter24Main {

    public static void main(String[] ars) {
        System.out.println("-------------------------SingleSource_BellmanFord-----------------------------");

        SingleSource_BellmanFord.EdgeNode s = new SingleSource_BellmanFord.EdgeNode('s', 0);
        SingleSource_BellmanFord.EdgeNode t = new SingleSource_BellmanFord.EdgeNode('t', 1);
        SingleSource_BellmanFord.EdgeNode x = new SingleSource_BellmanFord.EdgeNode('x', 2);
        SingleSource_BellmanFord.EdgeNode y = new SingleSource_BellmanFord.EdgeNode('y', 3);
        SingleSource_BellmanFord.EdgeNode z = new SingleSource_BellmanFord.EdgeNode('z', 4);

        SingleSource_BellmanFord.insert(s, new SingleSource_BellmanFord.EdgeNode('t', 1), 6);
        SingleSource_BellmanFord.insert(s, new SingleSource_BellmanFord.EdgeNode('y', 3), 7);
        SingleSource_BellmanFord.insert(t, new SingleSource_BellmanFord.EdgeNode('y', 3), 8);
        SingleSource_BellmanFord.insert(t, new SingleSource_BellmanFord.EdgeNode('x', 2), 5);
        SingleSource_BellmanFord.insert(t, new SingleSource_BellmanFord.EdgeNode('z', 4), -4);
        SingleSource_BellmanFord.insert(y, new SingleSource_BellmanFord.EdgeNode('x', 2), -3);
        SingleSource_BellmanFord.insert(y, new SingleSource_BellmanFord.EdgeNode('z', 4), 9);
        SingleSource_BellmanFord.insert(x, new SingleSource_BellmanFord.EdgeNode('t', 1), -2);
        SingleSource_BellmanFord.insert(z, new SingleSource_BellmanFord.EdgeNode('s', 0), 2);
        SingleSource_BellmanFord.insert(z, new SingleSource_BellmanFord.EdgeNode('x', 2), 7);

        SingleSource_BellmanFord.Graph G = new SingleSource_BellmanFord.Graph();
        G.adjList.add(new SingleSource_BellmanFord.VertexNode(s));
        G.adjList.add(new SingleSource_BellmanFord.VertexNode(t));
        G.adjList.add(new SingleSource_BellmanFord.VertexNode(x));
        G.adjList.add(new SingleSource_BellmanFord.VertexNode(y));
        G.adjList.add(new SingleSource_BellmanFord.VertexNode(z));

        G.numEdges = 10;
        G.numVertexes = 5;

        boolean rs = SingleSource_BellmanFord.bellmanFord(G, s);
        if (rs) {
            for (SingleSource_BellmanFord.VertexNode u : G.adjList) {
                if (u.firstEdge.pai != null) {
                    System.out.println(u.firstEdge.pai.key + "->" + u.firstEdge.key);
                }
            }
        }

        System.out.println("-------------------------SingleSource_DAG-----------------------------");

        SingleSource_DAG.EdgeNode s1 = new SingleSource_DAG.EdgeNode('s', 0);
        SingleSource_DAG.EdgeNode t1 = new SingleSource_DAG.EdgeNode('t', 1);
        SingleSource_DAG.EdgeNode x1 = new SingleSource_DAG.EdgeNode('x', 2);
        SingleSource_DAG.EdgeNode y1 = new SingleSource_DAG.EdgeNode('y', 3);
        SingleSource_DAG.EdgeNode z1 = new SingleSource_DAG.EdgeNode('z', 4);

        SingleSource_DAG.insert(s1, new SingleSource_DAG.EdgeNode('t', 1), 6);
        SingleSource_DAG.insert(s1, new SingleSource_DAG.EdgeNode('y', 3), 7);
        SingleSource_DAG.insert(t1, new SingleSource_DAG.EdgeNode('y', 3), 8);
        SingleSource_DAG.insert(t1, new SingleSource_DAG.EdgeNode('x', 2), 5);
        SingleSource_DAG.insert(t1, new SingleSource_DAG.EdgeNode('z', 4), -4);
        SingleSource_DAG.insert(y1, new SingleSource_DAG.EdgeNode('x', 2), -3);
        SingleSource_DAG.insert(y1, new SingleSource_DAG.EdgeNode('z', 4), 9);
        SingleSource_DAG.insert(x1, new SingleSource_DAG.EdgeNode('t', 1), -2);
        SingleSource_DAG.insert(z1, new SingleSource_DAG.EdgeNode('s', 0), 2);
        SingleSource_DAG.insert(z1, new SingleSource_DAG.EdgeNode('x', 2), 7);

        SingleSource_DAG.Graph G1 = new SingleSource_DAG.Graph();
        G1.adjList.add(new SingleSource_DAG.VertexNode(s1));
        G1.adjList.add(new SingleSource_DAG.VertexNode(t1));
        G1.adjList.add(new SingleSource_DAG.VertexNode(x1));
        G1.adjList.add(new SingleSource_DAG.VertexNode(y1));
        G1.adjList.add(new SingleSource_DAG.VertexNode(z1));

        G1.numEdges = 10;
        G1.numVertexes = 5;

        SingleSource_DAG.DAGShortestPaths(G1, s1);
        for (SingleSource_DAG.VertexNode u : G1.adjList) {
            if (u.firstEdge.pai != null) {
                System.out.println(u.firstEdge.pai.key + "->" + u.firstEdge.key);
            }
        }


        System.out.println("-------------------------SingleSource_Dijkstra-----------------------------");

        SingleSource_Dijkstra.EdgeNode s2 = new SingleSource_Dijkstra.EdgeNode('s', 0);
        SingleSource_Dijkstra.EdgeNode t2 = new SingleSource_Dijkstra.EdgeNode('t', 1);
        SingleSource_Dijkstra.EdgeNode x2 = new SingleSource_Dijkstra.EdgeNode('x', 2);
        SingleSource_Dijkstra.EdgeNode y2 = new SingleSource_Dijkstra.EdgeNode('y', 3);
        SingleSource_Dijkstra.EdgeNode z2 = new SingleSource_Dijkstra.EdgeNode('z', 4);

        SingleSource_Dijkstra.insert(s2, new SingleSource_Dijkstra.EdgeNode('t', 1), 10);
        SingleSource_Dijkstra.insert(s2, new SingleSource_Dijkstra.EdgeNode('y', 3), 5);
        SingleSource_Dijkstra.insert(t2, new SingleSource_Dijkstra.EdgeNode('y', 3), 2);
        SingleSource_Dijkstra.insert(t2, new SingleSource_Dijkstra.EdgeNode('x', 2), 1);
        SingleSource_Dijkstra.insert(y2, new SingleSource_Dijkstra.EdgeNode('t', 1), 3);
        SingleSource_Dijkstra.insert(y2, new SingleSource_Dijkstra.EdgeNode('x', 2), 9);
        SingleSource_Dijkstra.insert(y2, new SingleSource_Dijkstra.EdgeNode('z', 4), 2);
        SingleSource_Dijkstra.insert(x2, new SingleSource_Dijkstra.EdgeNode('z', 4), 4);
        SingleSource_Dijkstra.insert(z2, new SingleSource_Dijkstra.EdgeNode('s', 0), 7);
        SingleSource_Dijkstra.insert(z2, new SingleSource_Dijkstra.EdgeNode('x', 2), 6);

        SingleSource_Dijkstra.Graph G2 = new SingleSource_Dijkstra.Graph();
        G2.adjList.add(new SingleSource_Dijkstra.VertexNode(s2));
        G2.adjList.add(new SingleSource_Dijkstra.VertexNode(t2));
        G2.adjList.add(new SingleSource_Dijkstra.VertexNode(x2));
        G2.adjList.add(new SingleSource_Dijkstra.VertexNode(y2));
        G2.adjList.add(new SingleSource_Dijkstra.VertexNode(z2));

        G2.numEdges = 10;
        G2.numVertexes = 5;

        SingleSource_Dijkstra.Dijkstra(G2, s2);
        for (SingleSource_Dijkstra.VertexNode u : G2.adjList) {
            if (u.firstEdge.pai != null) {
                System.out.println(u.firstEdge.pai.key + "->" + u.firstEdge.key);
            }
        }
    }
}
